package top.minuy.subject.leetcode._695;

import java.util.ArrayList;

/**
 * 695. 岛屿的最大面积
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 * <p>
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 * <p>
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 * <p>
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 输出：6
 * 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 * 示例 2：
 * <p>
 * 输入：grid = [[0,0,0,0,0,0,0,0]]
 * 输出：0
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] 为 0 或 1
 * 通过次数140,882提交次数211,273
 *
 * @author Minuy
 * @time 13:46
 * @date 2021/11/20
 */
public class Solution1 {
    int V;
    int m, n;
    int[][] dirs4 = {
            /*{-1, -1},*/ {-1, 0}, /*{-1,  1},*/
            {0, -1}, /*{ 0,  0},*/ {0, 1},
            /*{ 1, -1},*/ {1, 0}, /*{ 1,  1},*/
    };
    boolean[] isVisited;
    int[][] grid;

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null) {
            return 0;
        }

        m = grid.length; // x
        if (m == 0) {
            return 0;
        }

        n = grid[0].length; // y
        if (n == 0) {
            return 0;
        }

        this.grid = grid;
        V = m * n;

        isVisited = new boolean[V];

        int maxArea = 0;
        for (int v = 0; v < V; v++) {
            int x = v / n;
            int y = v % n;
            if (!isVisited[v] && grid[x][y] == 1) {
                int count = bfs(v);
                maxArea = Math.max(maxArea, count);
            }
        }
        return maxArea;
    }

    private int bfs(int v) {
        int count = 0;
        ArrayList<Integer> queue = new ArrayList<>();
        queue.add(v);
        isVisited[v] = true;
        while (!queue.isEmpty()) {
            v = queue.remove(0);

            count++;

            int x = v / n;
            int y = v % n;

            for (int[] ints : dirs4) {
                int x1 = x + ints[0];
                int y1 = y + ints[1];
                if (x1 >= 0 && y1 >= 0 && x1 < m && y1 < n && grid[x1][y1] == 1) {
                    int v1 = x1 * n + y1;
                    if (!isVisited[v1]) {
                        queue.add(v1);
                        isVisited[v1] = true;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] l = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};

        System.out.println(new Solution1().maxAreaOfIsland(l));
    }
}
